﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SudokuWinForms
{
    public class Grid
    {
        public List<List<List<char>>> cells;

        public Grid()
        {
            cells = Repeat(() => Repeat(() => Range(9), 9), 9);
        }

        public List<char> this[int row, int col]
        {
            get { return cells[row][col]; }
        }
        
        private static List<T> Repeat<T>(Func<T> func, int count)
        {
            var list = new List<T>();
            for (int i = 0; i < count; ++i)
                list.Add(func());
            return list;
        }

        private static List<char> Range(int count)
        {
            var list = new List<char>();
            for (char i = 'A'; i <= 'I'; ++i)
                list.Add(i);
            return list;
        }

        public void Set(int row, int col, char ch)
        {
            cells[row][col].Clear();
            cells[row][col].Add(ch);
        }

        public void RemoveAll(int row, int col, IEnumerable<char> ch)
        {
            cells[row][col].RemoveAll(x => ch.Contains(x));
        }

        public void Reset(int row, int col)
        {
            cells[row][col] = Range(9);
        }

        public IEnumerable<List<List<char>>> Rows
        {
            get { return Enumerable.Range(0, 9).Select(Row); }
        }

        public IEnumerable<List<List<char>>> Cols
        {
            get { return Enumerable.Range(0, 9).Select(Col); }
        }

        public IEnumerable<List<List<char>>> Boxes
        {
            get { return Enumerable.Range(0, 9).Select(x => Box(x)); }
        }

        public List<List<char>> Row(int row)
        {
            return cells[row];
        }

        public List<List<char>> Col(int col)
        {
            return cells.Select(x => x[col]).ToList();
        }

        public List<List<char>> Box(int row, int col)
        {
            return Box(((row / 3) * 3) + (col / 3));
        }

        public List<List<char>> Box(int box)
        {
            return cells.Skip((box / 3) * 3).Take(3).SelectMany(x => x.Skip((box % 3) * 3).Take(3)).ToList();
        }

        public List<List<char>> RowExcept(int row, int col)
        {
            return Row(row).Where((x, i) => i != col).ToList();
        }

        public List<List<char>> ColExcept(int row, int col)
        {
            return Col(col).Where((x, i) => i != row).ToList();
        }

        public List<List<char>> BoxExcept(int row, int col)
        {
            return Box(row, col).Where((x, i) => ! (((i / 3) == (row % 3)) && ((i % 3) == (col % 3)))).ToList();
        }

        public void Reduce()
        {
            foreach (var row in Enumerable.Range(0, 9))
                foreach (var col in Enumerable.Range(0, 9))
                    Reduce(row, col);
        }

        public void Reduce(int row, int col)
        {
            if (cells[row][col].Count <= 1)
                return;

            var certains = Row(row).Where(x => x.Count == 1).Select(x => x[0]).Concat(
                Col(col).Where(x => x.Count == 1).Select(x => x[0]).Concat(
                    Box(row, col).Where(x => x.Count == 1).Select(x => x[0]))).Distinct().ToList();

            RemoveAll(row, col, certains);
        }

        public void Deduce()
        {
            foreach (var row in Enumerable.Range(0, 9))
                foreach (var col in Enumerable.Range(0, 9))
                    Deduce(row, col);
        }

        public void Deduce(int row, int col)
        {
            if (cells[row][col].Count <= 1)
                return;

            foreach (var val in cells[row][col])
            {
                bool noOtherInRow = RowExcept(row, col).All(x => ! x.Contains(val));
                bool noOtherInCol = ColExcept(row, col).All(x => ! x.Contains(val));
                bool noOtherInBox = BoxExcept(row, col).All(x => ! x.Contains(val));

                if (noOtherInRow || noOtherInCol || noOtherInBox)
                {
                    Set(row, col, val);
                    return;
                }
            }
        }

        public bool Validate()
        {
            foreach (int row in Enumerable.Range(0, 9))
            {
                foreach (int col in Enumerable.Range(0, 9))
                {
                    var cell = cells[row][col];

                    if ((cell.Count == 0) || ((cell.Count == 1) &&
                        ((RowExcept(row, col).Any(x => (x.Count == 1) && (x[0] == cell[0])))
                            || (ColExcept(row, col).Any(x => (x.Count == 1) && (x[0] == cell[0])))
                            || (BoxExcept(row, col).Any(x => (x.Count == 1) && (x[0] == cell[0]))))))
                            return false;
                }
            }

            return true;
        }

        public String FindBranch()
        {
            var branchGroups = new List<Tuple<String, List<List<char>>>>();

            foreach (var row in Rows)
            {
                var group = FindBranch(row);
                if (group != null)
                    branchGroups.Add(Tuple.Create("Row", group));
            }

            foreach (var col in Cols)
            {
                var group = FindBranch(col);
                if (group != null)
                    branchGroups.Add(Tuple.Create("Col", group));
            }

            foreach (var box in Boxes)
            {
                var group = FindBranch(box);
                if (group != null)
                    branchGroups.Add(Tuple.Create("Box", group));
            }

            return String.Join(" | ", branchGroups.Select(x => "[" + x.Item1 + "] " + String.Join(" : ", x.Item2.Select(y => String.Join(",", y)))));
        }

        public List<List<Pos>> FindBranchPoses()
        {
            var branchGroups = new List<List<Pos>>();

            foreach (var row in RowPoses)
            {
                var group = FindBranch(row);
                if (group != null)
                    branchGroups.Add(group);
            }

            foreach (var col in ColPoses)
            {
                var group = FindBranch(col);
                if (group != null)
                    branchGroups.Add(group);
            }

            foreach (var box in BoxPoses)
            {
                var group = FindBranch(box);
                if (group != null)
                    branchGroups.Add(group);
            }

            return branchGroups;
        }
        
        public List<Pos> ChooseBranch()
        {
            return FindBranchPoses().OrderBy(x => x.Count).FirstOrDefault();
        }

        private List<List<char>> FindBranch(IEnumerable<List<char>> group)
        {
            var undeterminedGroup = group.Where(x => x.Count > 1);

            if (! undeterminedGroup.Any())
                return null;

            var minPossibilityCount = undeterminedGroup.Min(x => x.Count);
            var cellsWithThatMany = group.Where(x => x.Count == minPossibilityCount).ToList();

            if (cellsWithThatMany.Count != undeterminedGroup.Count())
                return null;

            if (AllEqual(cellsWithThatMany))
                return cellsWithThatMany;

            return null;
        }

        private List<Pos> FindBranch(List<Pos> group)
        {
            var undeterminedGroup = group.Where(x => cells[x.Row][x.Col].Count > 1);

            if (! undeterminedGroup.Any())
                return null;

            var minPossibilityCount = undeterminedGroup.Min(x => cells[x.Row][x.Col].Count);
            var cellsWithThatMany = group.Where(x => cells[x.Row][x.Col].Count == minPossibilityCount).ToList();

            if (cellsWithThatMany.Count != undeterminedGroup.Count())
                return null;

            if (AllEqual(cellsWithThatMany))
                return cellsWithThatMany;

            return null;
        }

        private bool AllEqual(IEnumerable<List<char>> group)
        {
            if (group.Count() == 0)
                return false;
            else if (group.Count() == 1)
                return true;

            return group.Skip(1).All(g => Compare(g, group.First()));
        }

        private bool AllEqual(List<Pos> group)
        {
            if (group.Count() == 0)
                return false;
            else if (group.Count() == 1)
                return false;

            return group.Skip(1).All(g => Compare(cells[g.Row][g.Col], cells[group.First().Row][group.First().Col]));
        }

        private bool Compare(List<char> a, List<char> b)
        {
            if (a.Count != b.Count)
                return false;

            return a.Zip(b, (x, y) => x == y).All(x => x);
        }

        public List<List<Pos>> RowPoses
        {
            get { return Enumerable.Range(0, 9).Select(RowPos).ToList(); }
        }

        public List<List<Pos>> ColPoses
        {
            get { return Enumerable.Range(0, 9).Select(ColPos).ToList(); }
        }

        public List<List<Pos>> BoxPoses
        {
            get { return Enumerable.Range(0, 9).Select(BoxPos).ToList(); }
        }

        public List<Pos> RowPos(int row)
        {
            return Enumerable.Range(0, 9).Select(col => new Pos(row, col)).ToList();
        }

        public List<Pos> ColPos(int col)
        {
            return Enumerable.Range(0, 9).Select(row => new Pos(row, col)).ToList();
        }

        public List<Pos> BoxPos(int box)
        {
            return Enumerable.Range(0, 9).Select(i => new Pos((box / 3) + (i / 3), ((box % 3) * 3) + (i % 3))).ToList();
        }

        public List<List<char>> Get(List<Pos> poses)
        {
            return poses.Select(x => cells[x.Row][x.Col]).ToList();
        }

        public Grid Copy()
        {
            var newGrid = new Grid();
            newGrid.cells = cells.Select(x => new List<List<char>>(x.Select(y => new List<char>(y)))).ToList();
            return newGrid;
        }

        public bool IsSame(Grid that)
        {
            if (that == null)
                return false;

            foreach (var r in Enumerable.Range(0, 9))
            {
                foreach (var c in Enumerable.Range(0, 9))
                {
                    if (! Compare(this.cells[r][c], that.cells[r][c]))
                        return false;
                }
            }

            return true;
        }
    }

    public class Pos
    {
        public int Row { get; set; }
        public int Col { get; set; }
        public Pos(int row, int col) { Row = row; Col = col; }
        public override bool Equals(object obj)
        {
            if (obj == null || ! (obj is Pos)) return false;
            if (obj == this) return true;
            Pos p = (Pos) obj;
            return Row == p.Row && Col == p.Col;
        }
        public override int GetHashCode()
        {
            return Row ^ Col;
        }
        public override string ToString()
        {
            return "(" + Row + ", " + Col + ")";
        }
    }
}
